﻿// 7-14 根据后序和中序遍历输出先序遍历 (25 分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//user:lidongcheng
//date:20191113
//key:1.建立树的时候，先在后序里面挑后面的点，然后在中序里找这个点作比较，关键是始末坐标的变动，这个太复杂了
		//2.层序遍历，首先要注意队列是用二叉树指针类型，把根放入队列，然后不断读队列头指针是不是空，再将队头的左右孩子放入队列。
#include <iostream>
#include<string>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
class TreeNode
{

public:
	int data;
	TreeNode* lchild;
	TreeNode* rchild;
	TreeNode()
	{
		data = 0;
		TreeNode* lchild = NULL;
		TreeNode* rchild = NULL;

	}


	void visit_read() {
		if (data != '#')
		{
			cout << data;
			if (1) { cout << " "; }
		}

	}
	void cengxubianli(TreeNode* proot,int n) 
	{//通过检测队头的叶节点（注意不是域里面的数据）
		queue<TreeNode*> s;
		s.push(proot);
		int i = 0;
		while (!s.empty())
		{
			cout << s.front()->data;
			if (i != n - 1) { cout << " "; }
			
			if(s.front()->lchild!=NULL)
			{
				s.push(s.front()->lchild);
			}
			if (s.front()->rchild != NULL)
			{
				s.push(s.front()->rchild);
			}
			s.pop();
			i++;
		}
	}

	void pretraversal_read(TreeNode* proot) {
		if (NULL != proot)
		{
			(proot)->visit_read();
			pretraversal_read(proot->lchild);
			pretraversal_read(proot->rchild);
		}
	}


};

TreeNode* restoretree(int h1, int h2,int z1,int z2,int*hou,int*zhong)
{
	TreeNode* node = new TreeNode;
	node->data = hou[h2];
	//cout << "后序"<<hou[h2];
	for (int i = z1; i <= z2; i++)
	{
		if (zhong[i] == hou[h2])
		{
			if (i != z1)
				node->lchild = (restoretree(h1, h1 + i - z1 - 1, z1, i - 1, hou, zhong));
			if (i != z2)
				node->rchild = (restoretree(h2 - z2 + i, h2 - 1, i + 1, z2, hou, zhong));
		}
	}
	return (node);
}



int main() {
	int i = 0;


	int n;
	int a;
	cin >> n;
	char c;
	int* hou = new int[n];
	int* zhong = new int[n];
	for (i = 0; i < n; i++) {
		cin >> a;
		hou[i]=a;
	}
	for (i = 0; i < n; i++) {
		cin >> a;
		 zhong[i]=a;
	}
	int h1, h2;
	int z1, z2;
	z1 = h1 = 0;
	z2 = h2 = n-1;



TreeNode* head = new TreeNode;
	
head = restoretree(h1, h2, z1, z2, hou, zhong);

head->cengxubianli(head,n);//遍历二叉树


	



}